/**
 * 链表实现的队列
*/
#include <stdio.h>
#include <stdlib.h>

#ifndef QUEUE
#define QUEUE

// 队列元素类型
#ifndef QueueElementType
#define QueueElementType int
#endif

typedef struct LinkedNode LinkedNode;
struct LinkedNode {
    QueueElementType data;
    LinkedNode* prev;
    LinkedNode* next;
};

typedef struct Queue Queue;
struct Queue {
    int size;
    // 使用观察哨节点
    LinkedNode* sentinel;
};

LinkedNode* createLinkedNode(QueueElementType data, LinkedNode* prev, LinkedNode* next) {
    LinkedNode* node = (LinkedNode*)malloc(sizeof(LinkedNode));
    node->data = data;
    node->prev = prev;
    node->next = next;
    return node;
}

Queue* createQueue() {
    Queue* queue = (Queue*) malloc(sizeof(Queue));
    queue->sentinel = createLinkedNode(0, NULL, NULL);
    queue->sentinel->prev = queue->sentinel->next = queue->sentinel;
    queue->size = 0;
    return queue;
}

void freeQueue(Queue* queue) {
    for (LinkedNode* node = queue->sentinel->next; node != queue->sentinel; ) {
        LinkedNode* next = node->next;
        free(node);
        node = next;
    }
    free(queue->sentinel);
    free(queue);
}

int isEmptyQueue(Queue *queue) {
    return queue->size <= 0;
}

void enQueue(Queue *queue, QueueElementType data) {
    LinkedNode* node = createLinkedNode(data, queue->sentinel->prev, queue->sentinel);
    queue->sentinel->prev->next = node;
    queue->sentinel->prev = node;
    queue->size++;
}

QueueElementType deQueue(Queue* queue) {
    if (isEmptyQueue(queue)) {
        fprintf(stderr, "Queue is empty\n");
        exit(1);
    }
    // 出队列, 从链表中取出第一个节点
    LinkedNode* node = queue->sentinel->next;
    queue->sentinel->next = node->next;
    node->next->prev = queue->sentinel;
    queue->size--;
    // 取数据
    QueueElementType data = node->data;
    // 释放内存
    free(node);
    return data;
}

#endif
